package mo.leetcode_top;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class L763 {

    public List<Integer> partitionLabels(String s) {
        List<Integer>[] index = new ArrayList[26];
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            List<Integer> same = index[charArray[i]-'a'];
            if (same == null) {
                same = new ArrayList<>();
            }
            same.add(i);
            index[charArray[i]-'a'] = same;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < charArray.length; i++) {
            List<Integer> indexes = index[charArray[i]-'a'];
            int max = indexes.get(indexes.size()-1);
            for (int j = i+1; j < max; j++) {
                List<Integer> middle = index[charArray[j]-'a'];
                int compare = middle.get(middle.size() - 1);
                if (compare > max) {
                    max = compare;
                }
            }
            res.add(max-i+1);
            i = max;
        }
        return res;


    }

    public List<Integer> partitionLabelsBetter(String s) {
        List<Integer> list = new LinkedList<>();
        char[] chars = s.toCharArray();
        int[] scope = new int[26];//record the character's right bound

        for (int i = 0; i < chars.length; i++) {
            scope[chars[i] - 'a'] = i;
        }

        int last = -1;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            index = Math.max(index, scope[chars[i] - 'a']);
            if (i == index) {
                list.add(index - last);
                last = i;
            }
        }

        return list;
    }

    public static void main(String[] args) {
        L763 test = new L763();
        System.out.println(test.partitionLabels("ababcbacadefegdehijhklij"));
    }
}
